The present invention generally concerns compilers for generating computer code, and more particularly, dynamic-compilation systems that are used to generate executable instructions for selected parts of computer programs at run time.
Selective dynamic compilation transforms selected parts of computer programs at run time, using information available only at run time to optimize execution of the programs. A compilation strategy is employed during selective dynamic compilation to enable the code-compilation process to be completed in stagesxe2x80x94at static compile time, at link time, at load time, and (on demand) at run time. By delaying a portion of the compilation process, it is possible to take advantage of information available only at the later stages, with the goal of improving performance of the resulting code.
Postponing a portion of the compilation process until run time is called selective dynamic compilation and should not be confused with complete dynamic compilation, wherein all program compilation is done at run time. (Recently introduced xe2x80x9cjust in timexe2x80x9d compilers for JAVA are examples of complete dynamic compilers.) As used in this specification and in the claims that follow, the term xe2x80x9cdynamic compilationxe2x80x9d refers only to selective dynamic compilation and not to complete dynamic compilation.
Value-specific selective dynamic compilers derive their benefits by optimizing parts of programs for particular run-time computed values of invariant variables and data structures (called run-time constants), in effect, performing a kind of dynamic constant propagation and folding. Programs and program portions that are suitable for selective dynamic compilation include: (a) highly parameterized computations that use a significant amount of time consulting parameters, but often run using the same parameter settings; (b) programs with many similar subcomputations; (c) programs of highly interpretive nature, e.g., circuit and other simulators, where specializations remove the time to scan the object being simulated; and (d) database query search algorithm. Additional proposed applications for selective, value-specific dynamic compilation include specializing architectural simulators for the configuration being simulated, language interpreters for the program being interpreted, rendering engines for scene-specific state variables, numeric programs for dimensions and values of frequently used arrays, and critical paths in operating systems for the type of data being processed and the current state of the system. Trends in software engineering that are moving toward dynamic reconfigurability, such as parameterization for reuse and portability across different hardware architectures, also imply a promising role for dynamic compilation.
The principle challenge and trade-off in selective dynamic compilation is achieving high-quality dynamically generated code at low run-time cost, since the time to perform run-time compilation and optimization must be recovered before any benefit from dynamic compilation can be obtained. Consequently, a key design issue in developing an effective dynamic-compilation system is the method for determining where, when, and on what run time state to apply dynamic compilation. Ideally, the compiler would make these decisions automatically, as in other (static) compiler optimizations; however, this ideal is beyond current state of the art for general-purpose systems.
Instead, current dynamic-compilation systems rely on some form of programmer direction to indicate where dynamic compilation is to be applied to program code. Some systems take an imperative or operational approach to user direction, requiring the user to explicitly construct, compose, and compile program fragments at run time. Imperative approaches can express a wide range of optimizations, but impose a substantial burden on the programmer to manually program the optimizations. Moreover, such a programming burden makes it difficult to effectively apply imperative approaches to large applications. An example of an imperative system, called xe2x80x9cC,xe2x80x9d is described by D. R. Engler, W. C. Hsieh, and M. F. Kaashoek in xe2x80x9cC: A language for high-level, efficient, and machine-independent dynamic code generation,xe2x80x9d Conference Record of POPL""96: 23rd ACM SIGPLAN_SIGACT Symposium on Principles of Programming Languages, pp. 131-144, January 1996.
As an alternative to the imperative approach, several dynamic-compilation systems take a declarative or transformational approach, with user annotations guiding the dynamic compilation process. Examples of declarative systems include xe2x80x9cTempo,xe2x80x9d described by C. Consel and F. Nxc3x6el in xe2x80x9cA general approach for run-time specialization and its application to C,xe2x80x9d Conference Record of POPL""96: 23rd ACM SIGPLAN_SIGACT Symposium on Principles of Programming Languages, pp. 131-144, January 1996; and xe2x80x9cFabius,xe2x80x9d described by M. Leone and P. Lee in xe2x80x9cOptimizing ML with Run-Time Code Generation, Proceedings of the ACM SIGPLAN ""96 Conference on Programming Language Design and Implementation, pages 137-148, May 1996. Each of these declarative approaches adapts ideas from partial evaluation, expressing dynamic compilation as run-time specialization, where known or static values correspond to a run-time state for which programs are specialized. To keep dynamic compilation costs low, these systems preplan the possible effects of dynamic optimizations statically, producing a specialized dynamic compiler tuned to the particular part of the program being dynamically optimized; this sort of preplanning is known as staging the optimization. Declarative approaches offer the advantages of an easier interface to dynamic compilation for the programmer and easier program understanding and debugging. However, declarative systems usually offer less expressiveness and control over the dynamic compilation process than do imperative systems. Furthermore, the limitations of previous declarative systems have prevented them from coping effectively with the more involved patterns of control and data flow found in some small and most large applications, causing them to miss optimization opportunities or forcing substantial rewriting of the code to fit the limitations of the system. It would therefore be desirable to develop a system and associated programming interface that provides the ease of use of a declarative system, with the control and flexibility of an imperative-type system.
The cost of dynamic code generation must be recovered before benefits from specialized code can be realized. One way to recover this cost is to reuse the specialized code when a program""s execution path reaches the same point. Unfortunately, it is not always possible to do this, because the values of the static variables for which the code was specialized may have changed, rendering the specialized code unreusable. Reuse is achieved by caching the specialized code when it is dynamically generated and then doing a cache lookup, based on the values of the static variables, to retrieve it when the code is executed again. Some prior art systems cache specialized code only at function entry points. This limitation restricts the granularity of code specialization and reuse to entire functions, eliminating opportunities for reusing portions of a function. Other systems aggressively reuse code by caching it at every specialized jump target. However, such frequent cache lookups cause unacceptable overhead in run-time code. It would therefore be desirable to produce a system that most efficiently uses caching of specialized code portions and associated cache lookups.
Another shortfall of the prior art systems is that they do not provide on-demand specialization at a sub-function level. On-demand specialization, also known as lazy specialization, enables specialization to be deferred until a portion of the program to be specialized is assured of being executed, thereby reducing both the amount of specialized code produced and the overhead required to produce such code. Furthermore, on-demand specialization within a function enables an aggressive form of loop specialization, called complete loop unrolling, wherein each iteration of a loop is specialized on demand, as it is about to execute. In the absence of on-demand specialization, specialization by complete loop unrolling is not guaranteed to terminate. In most prior art systems, on-demand specialization is restricted to specializing entire functions on different values of function arguments. However, it is often beneficial to lazily specialize parts of a program smaller than a function. Such parts may include a rarely taken side of a conditional branch, separate iterations of a loop, or a fragment of code within a function that uses a static variable.
Although there are some prior art systems that allow a limited set of optimizations other than specialization to be performed lazily on arbitrary parts of a program, these prior art systems provide unsuitable results. When these systems resume optimization after the deferral, they cannot: (a) use optimization information computed before the deferral; (b) produce optimized code for different instances of this optimization information; or, (c) defer optimization again when optimizing the initial deferred part of the program. Without these capabilities, these systems cannot add to their repertoire of optimizations specialization that specializes effectively across a deferral, specializes on promoted static variables, or provides complete loop-unrolling that is guaranteed to terminate. It would therefore be desirable to provide a system that supports on-demand specialization at arbitrary program points, since such on-demand specialization can be used to provide several performance benefits, including specialization at a sub-function level and support for complete loop unrolling.
A further limitation of the prior art systems relates to conditional specialization. Sometimes dynamic program optimizations improve performance, and at other times, they degrade it. Therefore, a programmer may wish to apply an optimization conditionally, that is, only when it can be ascertained that the optimization will benefit performance. Two opposing factors usually determine whether conditionally applying an optimization will be beneficial: the reliability of the condition, and the run-time overhead of applying the optimization. A condition that can formulate conditions based only on compile-time information is often unreliable. On the other hand, compile-time conditions incur no run-time overhead. Run-time conditions are more reliable, because more information about the program""s state and behavior is available at run time. Most prior art systems either do not support conditional specialization, or only provide conditional specialization based on compile-time conditions. It would be advantageous to provide a system that could support both compile-time and run-time specialization. Furthermore, it would be desirable to provide a system that enables a programmer to apply conditional specialization through an easy to use programming interface.
The present invention is directed to a system and method for performing selective dynamic compilation using run-time information that overcomes many of the limitations of the prior art. The system, called xe2x80x9cDyC,xe2x80x9d implements a declarative, annotation based dynamic compilation and contains a sophisticated form of partial evaluation binding-time analysis (BTA), including program-point-specific polyvariant division and specialization, and dynamic versions of traditional global and peephole optimizations. The system provides policies that govern the aggressiveness of specialization and caching. It allows these policies to be declaratively specified, enabling programmers to gain fine control over the dynamic compilation process. It also enables programmers to specialize programs across arbitrary edges, both at procedure boundaries and within procedures, and to specialize programs based on evaluation of arbitrary compile-time and run-time conditions.
According to a first aspect of the invention, a method is provided for specializing a computer program by using a set of annotated policies. The computer program to be specialized comprises source code that is processed to generate machine-executable instructions comprising statically compiled code portions and specialized code portions. The specialized code portions comprise dynamically-compiled instructions that are generated at run time so as to operate on variables and data structures, which are constant at run time and are thus called run-time constants. The policies define directions for generating the specialized code portions and for integrating the specialized code portions with the statically-compiled code portions. Each policy is associated with a program statement and a value. The program statements are used by a programmer to annotate the original source code of a program, enabling the programmer to assert fine control over the program""s specialization. The annotated program statements are placed in the source code at points where specialization is cost effectivexe2x80x94that is, the increase in performance provided by the specialization more than offsets the extra run-time overhead required to perform the specialization. Preferably, the policies are bound to their associated variables by generating a control flow graph (CFG) representation of the program""s procedures and performing an iterative data flow analysis over the CFG for each procedure to propagate a set of divisions that map the variables to the policy values defined by the statements in the annotated source code. The source code is then processed to generate the statically-compiled code portions and to create run-time specializers that dynamically compile the specialized code portions when the code portions are requested to be executed at run time, based on the bound policy values.
According to a second aspect of the invention, a method is provided for conditionally specializing a computer program. The method enables programmers to annotate source code with conditional statements based on arbitrary compile-time and run-time conditions. The conditional statements are evaluated at compile time and/or at run time to determine which portions of a program are to be specialized. The specialized code portions preferably comprise a run-time specializer with a prepended specializer stub used to control the execution of the specialized code portion at run time.
According to another aspect of the invention, a method is provided for positioning cache lookups within a specialized computer program. The cache lookups are used to identify portions of a computer program that have already been specialized and are placed at locations within the program suitable for specialization. This method first identifies ranges within the dynamically-compiled portions of the program where the potential for code reuse might arise, wherein each range corresponds to a run-time constant and spans program points over which the run-time constant is operated on by the specialized code. These ranges are then coalesced by forming intersections between ranges that span common program points, preferably on a procedure-by-procedure basis. The cache lookups are then placed within the coalesced ranges, thereby reducing the number of cache lookup for a given program.
According to another aspect of the invention, a method is provided for enabling on-demand specialization across arbitrary control flow edges. Given a CFG representation of a computer program, and a particular edge in the CFG that connects two basic blocks, the method provides a mechanism for specializing the source block of the edge, while deferring the specialization of a destination block until the specialized version of the source block and the edge are executed, thereby creating a method for lazy (i.e., on-demand) specialization. The edge connecting the source block to the destination block is replaced with code that generates a stub, which is executed immediately after execution of the source block. The stub gathers values of the variables that are used in determining the specialization of the destination block, and invokes a specializer routine to create a specialized version of the destination block with respect to the gathered variable values.
According to another aspect of the invention, a system is provided for implementing the methods discussed above. The system includes a memory in which a plurality of machine instructions comprising a compiler are stored, and the memory is coupled to a processor that executes the machine instructions to perform the steps of the foregoing methods. The machine instructions preferably instruct the processor to create run-time specializers by generating extensions that dynamically compile the specialized code portions when the code portions are requested to be executed at run time, based on the annotated policies and/or conditional statements in a program""s source code. The generating extensions allow the program to be distributed as a stand-alone application.